翻訳と辞書 Words near each other ・ Turing (programming language) ・ Turing Award ・ Turing baronets ・ Turing completeness ・ Turing degree ・ Turing equivalence ・ Turing Foundation ・ Turing Institute ・ Turing jump ・ Turing Lecture ・ Turing machine ・ Turing Machine (band) ・ Turing machine equivalents ・ Turing machine examples ・ Turing machine gallery ・ Turing reduction ・ Turing switch ・ Turing tables ・ Turing tarpit ・ Turing test ・ Turing test (disambiguation) ・ Turing's proof ・ Turing+ ・ Turingery ・ Turini ・ Turino Vanni ・ Turinsk ・ Turinsky ・ Turinsky District ・ Turin–Ceres railway Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Turing reduction ： ウィキペディア英語版 Turing reduction In computability theory, a Turing reduction from a problem ''A'' to a problem ''B'', is a reduction which solves ''A'', assuming the solution to ''B'' is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve ''A'' if it had available to it a subroutine for solving ''B''. More formally, a Turing reduction is a function computable by an oracle machine with an oracle for ''B''. Turing reductions can be applied to both decision problems and function problems. If a Turing reduction of ''A'' to ''B'' exists then every algorithm for ''B'' can be used to produce an algorithm for ''A'', by inserting the algorithm for ''B'' at each place where the oracle machine computing ''A'' queries the oracle for ''B''. However, because the oracle machine may query the oracle a large number of times, the resulting algorithm may require more time asymptotically than either the algorithm for ''B'' or the oracle machine computing ''A'', and may require as much space as both together. The first formal definition of relative computability, then called relative reducibility, was given by Alan Turing in 1939 in terms of oracle machines. Later in 1943 and 1952 Stephen Kleene defined an equivalent concept in terms of recursive functions. In 1944 Emil Post used the term "Turing reducibility" to refer to the concept. A polynomial-time Turing reduction is known as a Cook reduction, after Stephen Cook. == Definition == Given two sets $A,B\; \backslash subseteq\; \backslash mathbb$ of natural numbers, we say $A$ is Turing reducible to $B$ and write :$A\; \backslash leq\_T\; B$ if there is an oracle machine that computes the characteristic function of ''A'' when run with oracle ''B''. In this case, we also say ''A'' is ''B''-recursive and ''B''-computable. If there is an oracle machine that, when run with oracle ''B'', computes a partial function with domain ''A'', then ''A'' is said to be ''B''-recursively enumerable and ''B''-computably enumerable. We say $A$ is Turing equivalent to $B$ and write $A\; \backslash equiv\_T\; B\backslash ,$ if both $A\; \backslash leq\_T\; B$ and $B\; \backslash leq\_T\; A.$ The equivalence classes of Turing equivalent sets are called Turing degrees. The Turing degree of a set $X$ is written $\backslash textbf(X)$. Given a set $\backslash mathcal\; \backslash subseteq\; \backslash mathcal(\backslash mathbb)$, a set $A\; \backslash subseteq\; \backslash mathbb$ is called Turing hard for $\backslash mathcal$ if $X\; \backslash leq\_T\; A$ for all $X\; \backslash in\; \backslash mathcal$. If additionally $A\; \backslash in\; \backslash mathcal$ then $A$ is called Turing complete for $\backslash mathcal$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Turing reduction」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.